package com.ztl.leetcode.SwordFingerOffer;

/**
 * @author @ztl
 * @ClassName:KNodeFromBottom_22
 * @Package:com.ztl.leetcode.SwordFingerOffer
 * @date 2023年05月15日 20:50
 * @description: 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * @version: 1.0
 */
public class KNodeFromBottom_22 {
    //总体遍历一次链表，时间复杂度O(n),使用常数空间存储变量，空间复杂度O(1)
    public ListNode getKthFromEnd(ListNode head, int k) {
        //思路：使用两个指针left和right作为快慢指针操作链表
        //right为快指针，先向右移动k个节点，然后left再和right同时向右移动
        //当right移动到终点时，left指向的就是倒数第k个节点
        //证明：设链表长度为10，k为3，right先移动3位，剩下7位；
        //此时left与right一起移动，到终点时left只能移动7位，也即是10-3=7，即倒数第3位；

        //定义慢指针left，快指针right，分别指向head；
        ListNode left=head,right=head;

        //快指针先移动k位
        for(int i=0;i<k;i++){
            right = right.next; //先让右指针移动k位
        }

        //快慢指针一起往前移动，当right指向空时，left移动了链表长度-k次；
        //也就是left最终指向倒数第k个节点
        while(right!=null){
            right = right.next;
            left = left.next;
        }

        //最后返回倒数第k个节点left
        return left;
    }
}
